package com.lun.swordtowardoffer2.c03;

public class LengthOfLongestSubstring {
	
	public int lengthOfLongestSubstring(String s) {		
		if(s.length() == 0) return 0;
		int[] counts = new int[256];
		int p1 = -1, p2 = 0, longest = 1;
		
		for(; p2 < s.length(); p2++) {
			counts[s.charAt(p2)]++;
			while(hasRepeatedOne(counts)) {
				counts[s.charAt(++p1)]--;
			}
			longest = Math.max(longest, p2 - p1);
		}
		
		return longest;
	}
	
	private boolean hasRepeatedOne(int[] count) {
		for(int num : count)
			if(num > 1) 
				return true;
		return false;
	}
	
	public int lengthOfLongestSubstring2(String s) {
		if(s.length() == 0) return 0;
		int[] counts = new int[256];
		int p1 = -1, p2 = 0, longest = 1, countDup = 0;
		
		for(; p2 < s.length(); p2++) {
			counts[s.charAt(p2)]++;
			if(counts[s.charAt(p2)] == 2)
				countDup++;
			
			while(countDup > 0) {
				counts[s.charAt(++p1)]--;
				
				if(counts[s.charAt(p1)] == 1)
					countDup--;
			}
			longest = Math.max(longest, p2 - p1);
		}
		
		return longest;
	}
}
